package com.zhy.algorithm;

/**
 * @author 随缘而愈
 * @version 1.0
 * @description 哈希查找（无序查找）
 * @date 23/3/2024 下午7:48
 */

public class HashSearch {
    private int[] array;
    private int capacity;

    public HashSearch(int capacity) {
        this.capacity = capacity;
        this.array = new int[capacity];
    }

    // 插入元素到哈希表
    public void insert(int key) {
        int index = hash(key);
        while (array[index] != 0 && array[index] != key) {
            index = (index + 1) % capacity; // 处理哈希冲突
            if (index == hash(key)) { // 如果回到原点仍未找到空位，则表已满
                throw new RuntimeException("Hash table is full.");
            }
        }
        array[index] = key;
    }

    // 哈希函数：简单取模运算
    private int hash(int key) {
        return key % capacity;
    }

    // 查找元素
    public boolean search(int key) {
        int index = hash(key);
        while (array[index] != 0) {
            if (array[index] == key) {
                return true; // 找到元素
            }
            index = (index + 1) % capacity; // 处理哈希冲突
            if (index == hash(key)) { // 如果回到原点仍未找到，则元素不存在
                break;
            }
        }
        return false; // 没找到元素
    }

    // 测试上述代码
    public static void main(String[] args) {
        HashSearch hashSearch = new HashSearch(10); // 创建一个容量为10的哈希表

        // 插入一些元素
        hashSearch.insert(5);
        hashSearch.insert(15);
        hashSearch.insert(25);
        hashSearch.insert(35);

        // 查找元素
        System.out.println(hashSearch.search(15)); // 输出: true
        System.out.println(hashSearch.search(20)); // 输出: false
    }
}
